#ifndef _H_STRUCTURE_KDTREE
#define _H_STRUCTURE_KDTREE
#include "../core/scene.hpp"
namespace chen {
class Kdtree : public Structure {
private:
    class Node {
    public:
        int l, r;
        Bound3 bnd;
        const Shape * s;
    } ;
    Node * d;
    int dtot;
    int build (int l, int r) ;
    int newNode () ;
    void query_x (int u, const Ray & r, SurfInteract * si, bool & b) const ;
    const Shape * query_y (int u, const Ray & r) const ;
public:
    Kdtree (const std::vector<const Shape*> & v) ;
    virtual bool castRay (const Ray & r, SurfInteract * si) const ;
    /*
    该函数不保证ray中的t为最小值！
    */
    virtual const Shape * testRay (const Ray & r) const ;
    ~Kdtree () ;
};
}
#endif